// m

// 给定一个非负整数数组nums，数组中每个元素代表在该位置可以跳跃的最大长度
// 开始位置为数组的第一个下标处，要求判断是否能够到达最后一个下标

// 解题思路
// 定义动态规划状态dp[i] 为，从0触发，经过j <= i，可以跳出的最远距离，可以得出：
// 1. dp[0] = nums[0],表示从0出发，经过0，可以跳出的最远距离为nums[0]
// 2. 如果能通过0~i-1个位置到达i，即dp[i-1]>=i， 则dp[i] = max(dp[i-1], i + nums[i])
// 3. 如果不能通过0~i-1个位置到达i，则dp[i-1] < i, 则dp[i] = dp[i-1]
function canJump(nums) {
    let size = nums.length
    let dp = new Array(size).fill(0)
    dp[0] = nums[0]
    for (let i = 1; i < size; i++) {
        if (i <= dp[i - 1]) {
            dp[i] = Math.max(dp[i - 1], i + nums[i])
        } else {
            dp[i] = dp[i - 1]
        }
    }
    return dp[size - 1] >= size - 1
}

let nums = [2, 3, 1, 1, 4]
console.log(canJump(nums))